package main

import "fmt"

func LCS(s1 string, s2 string) string {
	l1, l2 := len(s1), len(s2)
	dp := make([][]int, l1+1, l1+1)
	for i := range dp {
		dp[i] = make([]int, l2+1, l2+1)
	}

	for i := 1; i <= l1; i++ {
		for j := 1; j <= l2; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				if dp[i][j-1] > dp[i-1][j] {
					dp[i][j] = dp[i][j-1]
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
	}

	maxLen := dp[l1][l2]
	fmt.Println(maxLen)
	if maxLen <= 0 {
		return "-1"
	}

	buf := make([]byte, maxLen, maxLen)
	for maxLen > 0 {
		switch {
		case s1[l1-1] == s2[l2-1]:
			maxLen--
			buf[maxLen] = s1[l1-1]
			l1--
			l2--
		case dp[l1][l2] == dp[l1][l2-1]: // s2[l2-1]不在最长子序列中, 向前寻找
			l2--
		case dp[l1][l2] == dp[l1-1][l2]: // s1[l1-1]不在最长子序列中, 向前寻找
			l1--
		}
	}

	return string(buf)
}

func main() {
	s := LCS("1A2C3D4B56", "B1D23A456A")
	fmt.Println(s)
}
